// 给定一个长度为 n 的整数数组 nums，其中 n > 1，
// 设计算法返回输出数组 output ，要求 output[i] 等于在nums 中除 nums[i] 之外其余各元素的乘积。
// 条件：
// 1、时间复杂度要求小于等于On 
// 2、不能用除法

var productExceptSelf: (nums: number[]) => number[] = function (nums) {
    // 声明结果数组
    let res: number[] = [];
    // 初始化前缀积数组并计算
    res.push(1);
    for (let i = 1; i < nums.length; i++) {
        res[i] = res[i - 1] * nums[i - 1];
    }
    // 初始化后缀积变量并计算结果数组
    let pre: number = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        // 结果数组的第i位为前缀积数组第i位乘后缀积变量
        res[i] = res[i] * pre;
        // 维护变量pre
        pre = pre * nums[i];
    }
    return res;
};

        // 这道题考察的还是一个利用前缀数组、后缀数组的解法
        // 声明一个前缀数组，其中每个前缀数组元素对应为原数组该位置的前缀积
        // 如[2,3,4]的前缀数组就为[1,2,6]，这里注意前缀数组的首位元素为1！
        // 因为在原数组2的旁边是没有数的，这里初始化为 1 算积就很方便
        // 同理我们也声明一个后缀数组，例如[2,3,4]对应为[12,4,1]
        // 然后我们可以发现结果数组中的res[i] = 前缀数组[i]*后缀数组[i]
        // 三遍循环就可以得到结果
        // 但同时这道题也可以在空间复杂度上可以继续压缩，
        // 具体操作为前缀数组我们就直接用结果数组res来存储
        // 再计算后缀数组时我们不需要声明数组，直接声明一个后缀积变量
        // 然后逆序遍历前缀积数组，在每次遍历的过程中
        // 一边计算结果，一边维护这个后缀积变量
        // 可以把空间复杂度压缩为O（1）。